home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / SORT / SORT1.HLP < prev    next >
Text File  |  1989-01-24  |  2KB  |  48 lines
  1.          Name: SORT1
  2.          Type: Assembler Macro
  3.       Version: 1.0
  4.  Date Entered: 11-Sept-87
  5.   Last Change: 11-Sept-87
  6.  
  7.   Description: Sorting an Array by Straight Selection
  8.  
  9.  SORT1 is a programming example of sorting by "Straight Selection"
  10.  on the DSP56001.  The macro will sort an array of size "N_ITEMS"
  11.  in X memory space starting at location "ARRAY".
  12.  
  13.  SORT1 uses the straight selection algorithm to sort an ARRAY of
  14.  signed numbers.  The sort is performed "in-place" and requires no
  15.  additional memory locations.  The algorithm searches all items 
  16.  of the array to find the lowest valued item which is swapped with
  17.  the next item of the final sorted sequence [1].
  18.  
  19.  For SORT1 the execution time is proportional to the square of
  20.  the array size (N_ITEMS).  In this DSP56000 implementation the
  21.  execution time for SORT1 is constant for any given array size,
  22.  even if the array is already ordered, inversely ordered or
  23.  randomly ordered when the algorithm is executed.  The benchamarks
  24.  are for randomly ordered arrays.
  25.  
  26.  The SORT1 macro is efficient for sorting smaller arrays of numbers. 
  27.  SORT2 is more efficient for larger arrays.  
  28.                                  
  29.  Benchmark Performances for 20.5MHz DSP56001:
  30.  
  31.  Array Size             SORT1                   SORT2
  32.  (N_ITEMS)      (Straight Selection)         (Heapsort)
  33.  ----------     --------------------         ----------
  34.       8                 14.5us                  51.7us
  35.      16                 41.8us                  130us
  36.      32                 134us                   317us
  37.      64                 468us                   741us
  38.     128                 1.7ms                   1.7ms
  39.     256                 6.7ms                   4.0ms
  40.     512                26.1ms                   9.1ms
  41.  
  42.  
  43.  References
  44.  ----------
  45.  [1] Niklaus Wirth, "Algorithms + Data Structures = Programs,"
  46.  Prentice-Hall, 1976. pp. 63-65, Program 2.3.
  47.  
  48.